<html>
  <head>
	  <meta http-equiv="content-type" content="text/html; charset=utf-8" />
    <title>i5ting_ztree_toc:线性表（二）</title>
		<link href="toc/style/github-bf51422f4bb36427d391e4b75a1daa083c2d840e.css" media="all" rel="stylesheet" type="text/css"/>
		<link href="toc/style/github2-d731afd4f624c99a4b19ad69f3083cd6d02b81d5.css" media="all" rel="stylesheet" type="text/css"/>
		<link href="toc/css/zTreeStyle/zTreeStyle.css" media="all" rel="stylesheet" type="text/css"/>
	  <style>
		pre {
		    counter-reset: line-numbering;
		    border: solid 1px #d9d9d9;
		    border-radius: 0;
		    background: #fff;
		    padding: 0;
		    line-height: 23px;
		    margin-bottom: 30px;
		    white-space: pre;
		    overflow-x: auto;
		    word-break: inherit;
		    word-wrap: inherit;
		}

		pre a::before {
		  content: counter(line-numbering);
		  counter-increment: line-numbering;
		  padding-right: 1em; /* space after numbers */
		  width: 25px;
		  text-align: right;
		  opacity: 0.7;
		  display: inline-block;
		  color: #aaa;
		  background: #eee;
		  margin-right: 16px;
		  padding: 2px 10px;
		  font-size: 13px;
		  -webkit-touch-callout: none;
		  -webkit-user-select: none;
		  -khtml-user-select: none;
		  -moz-user-select: none;
		  -ms-user-select: none;
		  user-select: none;
		}

		pre a:first-of-type::before {
		  padding-top: 10px;
		}

		pre a:last-of-type::before {
		  padding-bottom: 10px;
		}

		pre a:only-of-type::before {
		  padding: 10px;
		}

		.highlight { background-color: #ffffcc } /* RIGHT */
		</style>
  </head>
  <body>
	  <div>
				<div style='width:25%;'>
						<ul id="tree" class="ztree" style='width:100%'>

						</ul>
				</div>
        <div id='readme' style='width:70%;margin-left:20%;'>
          	<article class='markdown-body'>
            	<h1 id="-">线性表（二）</h1>
<h3 id="81-ii"><a href="https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/">81. 搜索旋转排序数组 II</a></h3>
<p>已知存在一个按非降序排列的整数数组 <code>nums</code>（当i&gt;0且i&lt;nums.length,nums[i+1] &gt;= nums[i]） ，数组中的值不必互不相同。</p>
<p>在传递给函数之前，<code>nums</code> 在预先未知的某个下标 <code>k</code>（<code>0 &lt;= k &lt; nums.length</code>）上进行了 <strong>旋转</strong> ，使数组变为 <code>[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]</code>（下标 <strong>从 0 开始</strong> 计数）。例如， <code>[0,1,2,4,4,4,5,6,6,7]</code> 在下标 <code>5</code> 处经旋转后可能变为 <code>[4,5,6,6,7,0,1,2,4,4]</code> 。</p>
<p>给你 <strong>旋转后</strong> 的数组 <code>nums</code> 和一个整数 <code>target</code> ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 <code>nums</code> 中存在这个目标值 <code>target</code> ，则返回 <code>true</code> ，否则返回 <code>false</code> 。</p>
<h5 id="-1-"><strong>示例 1：</strong></h5>
<pre><code>输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
</code></pre><h5 id="-2-"><strong>示例 2：</strong></h5>
<pre><code>输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
</code></pre><hr>
<h5 id="-">解法</h5>
<p>思路：二分法，已知若无重复元素，则旋转后的数组从中间分开，一定有一边是有序的。</p>
<p>但因为数组里面的值可以重复，当nums[left]==nums[mid]==nums[right]的情况时，会出现两边无法判断那边是有序的情况。</p>
<p>因此二分判断加一项nums[left]==nums[mid]==nums[right]时，应该left++，right--，</p>
<p>之后进入二分判断：</p>
<ol>
<li><p>首先target大于mid上的值，直接返回mid</p>
</li>
<li><p>否则判断left的值是否小于等于right的值</p>
<p>是的话：</p>
<ul>
<li>target小于nums[mid]且大于等于nums[left]，则目标一定在左边</li>
<li>否则在右边</li>
</ul>
<p>否的话：</p>
<ul>
<li>target小于等于nums[right]且target大于nums[mid]，则目标一定是在右边</li>
<li>否则的话在左边</li>
</ul>
</li>
</ol>
<pre><code class="lang-java">class Solution {
    public boolean search(int[] nums, int target) {
        if(nums.length &lt; 1){
            return false;
        }
        int left = 0;
        int right = nums.length-1;
        while(left &lt;= right){
            int mid = left + ((right - left) &gt;&gt; 1);
            if(nums[mid] == target){
                return true;
            }else if(nums[left] == nums[mid]&amp;&amp;nums[mid]==nums[right]){
                right --;
                left++;
            }else if(nums[left]&lt;=nums[mid]){
                if(target&lt;nums[mid]&amp;&amp;target&gt;=nums[left]){
                    right = mid -1;
                }else{
                    left = mid + 1;
                }
            }else{
                if(target&gt;nums[mid]&amp;&amp;target&lt;=nums[right]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }
        return false;
    }
}
</code></pre>
<h3 id="4-"><a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/">4. 寻找两个正序数组的中位数</a></h3>
<p>难度困难4169</p>
<p>给定两个大小分别为 <code>m</code> 和 <code>n</code> 的正序（从小到大）数组 <code>nums1</code> 和 <code>nums2</code>。请你找出并返回这两个正序数组的 <strong>中位数</strong> 。</p>
<h5 id="-1-"><strong>示例 1：</strong></h5>
<pre><code>输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
</code></pre><h5 id="-2-"><strong>示例 2：</strong></h5>
<pre><code>输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
</code></pre><h5 id="-3-"><strong>示例 3：</strong></h5>
<pre><code>输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
</code></pre><h5 id="-4-"><strong>示例 4：</strong></h5>
<pre><code>输入：nums1 = [], nums2 = [1]
输出：1.00000
</code></pre><h5 id="-5-"><strong>示例 5：</strong></h5>
<pre><code>输入：nums1 = [2], nums2 = []
输出：2.00000
</code></pre><hr>
<h5 id="-1-">解法1：</h5>
<p>思路：归并排序之后直接取中位数</p>
<pre><code class="lang-java">class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        int[] nums = new int[len1 + len2];
        int i = 0, j = 0, n = 0;
        while (i &lt; len1 &amp;&amp; j &lt; len2) {
            if (nums1[i] &lt; nums2[j]) {
                nums[n] = nums1[i];
                i++;
            } else {
                nums[n] = nums2[j];
                j++;
            }
            n++;
        }

        if(i == len1){
            for(;j &lt; len2;j++){
                nums[n] = nums2[j];
                n++;
            }
        }

        if(j == len2){
            for(;i &lt; len1;i++){
                nums[n] = nums1[i];
                n++;
            }
        }

        if(nums.length == 1) return nums[0];

        if (nums.length % 2 == 0) {
            return (double)(nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2;
        } else {
            return nums[nums.length / 2];
        }
    }
}
</code></pre>
<h5 id="-">解法二</h5>
<p>思路：二分法，</p>
<p>可以归纳出三种情况：</p>
<ul>
<li>如果 A[k/2-1] &lt;  B[k/2-1]，则比A[k/2−1] 小的数最多只有 A 的前 k/2−1 个数和 B 的前k/2−1 个数，即比 A[k/2−1] 小的数最多只有 k-2个，因此 A[k/2−1] 不可能是第 k 个数，A[0] 到 A[k/2−1] 也都不可能是第 k 个数，可以全部排除。</li>
</ul>
<ul>
<li>如果 A[k/2-1] &gt; B[k/2-1]，则可以排除B[0] 到 B[k/2−1]。</li>
</ul>
<ul>
<li>如果 A[k/2−1]=B[k/2−1]，则可以归入第一种情况处理。</li>
</ul>
<p><img src="https://assets.leetcode-cn.com/solution-static/4/4_fig1.png" alt=""></p>
<ul>
<li>如果 A[k/2−1] 或者 B[k/2−1] 越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 k 的值，而不能直接将 k 减去 k/2。</li>
</ul>
<ul>
<li>如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。</li>
</ul>
<ul>
<li>如果 k=1，我们只要返回两个数组首元素的最小值即可。</li>
</ul>
<p>链接：<a href="https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/">https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/</a>
来源：力扣（LeetCode）</p>
<pre><code class="lang-java">class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if((len1 + len2)%2 == 1){
            //取第(len1 + len2)/2 + 1个值
            return getKThElement(nums1 , nums2 , (len1 + len2)/2 + 1);
        }else{
            //取第(len1 + len2)/2 个值和第(len1 + len2)/2 + 1个值的和除以2
            return (double)(getKThElement(nums1 , nums2 , (len1 + len2)/2) + getKThElement(nums1 , nums2 , (len1 + len2)/2+1))/2;
        }
    }

    public int getKThElement(int[] nums1,int[] nums2 ,int k){
        int index1 = 0;
        int index2 = 0;

        while(true){
            //如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k              //小的元素。
            if(index1 &gt;= nums1.length){
                return nums2[index2 + k - 1];
            }

            if(index2 &gt;= nums2.length){
                return nums1[index1 + k - 1];
            }
            // k=1，我们只要返回两个数组首元素的最小值即可
            if(k == 1){
                return Math.min(nums1[index1],nums2[index2]);
            }

            int half = k / 2;
            int newIndex1 = Math.min(index1 + half,nums1.length) - 1;
            int newIndex2 = Math.min(index2 + half,nums2.length) - 1;
            if(nums1[newIndex1] &lt;= nums2[newIndex2]){
                //排除掉前newIndex1 - index1 + 1位
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }else{
                //排除掉前newIndex2 - index2 + 1位
                k -=  (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}
</code></pre>
<h3 id="128-"><a href="https://leetcode-cn.com/problems/longest-consecutive-sequence/">128. 最长连续序列</a></h3>
<p>给定一个未排序的整数数组 <code>nums</code> ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。</p>
<p><strong>进阶：</strong>你可以设计并实现时间复杂度为 <code>O(n)</code> 的解决方案吗？</p>
<h4 id="-1-"><strong>示例 1：</strong></h4>
<pre><code>输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
</code></pre><h4 id="-2-"><strong>示例 2：</strong></h4>
<pre><code>输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
</code></pre><hr>
<h4 id="-1">解法1</h4>
<p>思路 : 排序后遍历数组，进行遍历贪心</p>
<pre><code class="lang-java">class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        Arrays.sort(nums);
        int res = 1;
        int max = 1;
        for(int i = 1;i &lt; nums.length;i ++ ){
            if(nums[i] == nums[i - 1] ) continue;
            if(nums[i] - nums[i - 1] == 1){
                res++;
                max = Math.max(res,max);
            }else{
                res = 1;
            }
        }
        return max;
    }
}
</code></pre>
<h4 id="-2">解法2</h4>
<p>思路：使用Set，for循环加入Set集合，然后在遍历一次数组取得结果</p>
<pre><code class="lang-java">class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        Set&lt;Integer&gt; set = new HashSet&lt;Integer&gt;();
        for(int i = 0;i &lt; nums.length;i++){
            set.add(nums[i]);
        }
        int res = 0;
        for(int i = 0;i &lt; nums.length;i++){
            if(!set.contains(nums[i] - 1)){
                int curLength = 1;
                int cur = nums[i] + 1;
                while(set.contains(cur)){
                    curLength++;
                    cur++;
                }
                res = Math.max(res,curLength);
            }
        }
        return res;
    }
}
</code></pre>
<h4 id="-">解法三</h4>
<p>思路：使用并查集</p>
<p>并查集是一种数组结构，里面都是键值对，键表示数值，值表示键的头结点</p>
<p>里面有两个方法</p>
<ul>
<li>union( x , y )方法，把 x 和 y 合并，将x、y的头节点变为同一个（一般选取高度大的头节点作为头节点）</li>
<li>find( target ) 方法，返回target的头节点</li>
</ul>
<p>首先在通过数组初始化并查集，之后遍历数组，在并查集里将当前的值与值+1进行union（若不存在则不合并）</p>
<p>则最终，在并查集里面每个点的头节点都会指向数组里面 递增为1 的最大值</p>
<pre><code class="lang-java">class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length == 0){
            return 0;
        }
        UnionFind union = new UnionFind(nums);

        for(int i = 0;i &lt; nums.length; i++){
            union.union(nums[i],nums[i] + 1);
        }
        int res = Integer.MIN_VALUE;
        for(int i = 0;i &lt; nums.length; i++){
            res = Math.max(union.find(nums[i]) - nums[i] + 1,res);
        }
        return res;
    }

    class UnionFind{
        Map&lt;Integer,Integer&gt; parent = new HashMap&lt;&gt;();
        int count;

        public UnionFind(int[] arr){
            for(Integer v:arr){
                parent.put( v , v);
            }
            count = parent.size();
        }

        public void union(Integer p,Integer q){
            Integer rootp = find(p);
            Integer rootq = find(q);

            if(rootp == null ||rootq == null){
                return;
            }

            if(rootp == rootq){
                return;
            }
            //p ，q(p + 1);故将q变为p的头
            parent.put(rootp,rootq);
            count --;
        }

        public Integer find(Integer v){
            if(!parent.containsKey(v)){
                return null;
            }

            Integer root = v;
            while(root != parent.get(root)){
                root = parent.get(root);
            }

            //扁平化并查集
            while(v != parent.get(v)){
                Integer cur = parent.get(v);
                v = parent.get(cur);
                parent.put(cur , root);
            }

            return root;
        }
    }
}
</code></pre>

          	</article>
        </div>
		</div>
  </body>
</html>
<script type="text/javascript" src="toc/js/jquery-1.4.4.min.js"></script>
<script type="text/javascript" src="toc/js/jquery.ztree.all-3.5.min.js"></script>
<script type="text/javascript" src="toc/js/ztree_toc.js"></script>
<script type="text/javascript" src="toc_conf.js"></script>

<SCRIPT type="text/javascript" >
<!--
$(document).ready(function(){
    var css_conf = eval(markdown_panel_style);
    $('#readme').css(css_conf)
    
    var conf = eval(jquery_ztree_toc_opts);
		$('#tree').ztree_toc(conf);
});
//-->
</SCRIPT>